home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programmierung
/
Power-Programmierung (Tewi)(1994).iso
/
magazine
/
pctchnqs
/
1991
/
number2
/
heap.cpp
< prev
next >
Wrap
C/C++ Source or Header
|
1991-04-02
|
3KB
|
101 lines
// ==========================================================
// Listing 2: heap.cpp
// C++ code implementing binary heaps.
// Copyright (C) 1991 by Nicholas Wilt. All rights reserved.
// ==========================================================
// Refer to the MAKEFILE listing (Listing 4) for dependencies
// ----------------------------------------------------------
#include <alloc.h>
#include "heap.h"
// --------------------------------------------------------------
// Constructor: Takes a pointer to a comparison function akin to
// those used by bsearch() and qsort().
// --------------------------------------------------------------
Heap::Heap(int (*ComparisonFunction)(void *, void *))
{
elms = (void **) malloc(DEFSIZE * sizeof(void *));
n = 0;
maxsize = DEFSIZE;
comp = ComparisonFunction;
}
// --------------------------------------------------------------
// Destructor: Free the allocated memory.
// --------------------------------------------------------------
Heap::~Heap()
{
free(elms);
}
// --------------------------------------------------------------
// SiftUp(): Restores the heap property if broken at the bottom.
// --------------------------------------------------------------
void Heap::SiftUp()
{
int i = n - 1;
while (i) {
int p = (i-1) >> 1;
void *temp;
if ((*comp)(elms[p], elms[i]) <= 0)
break;
temp = elms[i];
elms[i] = elms[p];
elms[p] = temp;
i = p;
}
}
// --------------------------------------------------------------
// SiftDown(): Restores the heap property if broken at the top.
// --------------------------------------------------------------
void Heap::SiftDown()
{
int i = 0;
int c;
while ( (c = i+i+1) < n) {
void *temp;
if (c+1 < n)
c += ((*comp)(elms[c+1], elms[c]) < 0);
if ((*comp)(elms[i], elms[c]) <= 0)
break;
temp = elms[i];
elms[i] = elms[c];
elms[c] = temp;
i = c;
}
}
// --------------------------------------------------------------
// Insert(): Insert an element into the heap and restore the heap
// property.
// --------------------------------------------------------------
void Heap::Insert(void *ptr)
{
if (++n >= maxsize) {
maxsize <<= 1;
elms = (void **) realloc(elms, maxsize * sizeof(void *));
}
elms[n-1] = ptr;
SiftUp();
}
// --------------------------------------------------------------
// Extract(): Extract the ranking element from the heap and
// restore the heap property.
// --------------------------------------------------------------
void *Heap::Extract()
{
void *ret;
if (! n)
return 0;
ret = elms[0];
elms[0] = elms[--n];
SiftDown();
return ret;
}